package 动态规划.跳跃游戏;

/**
 * author: shalock.lin
 * date: 2022/11/12
 * describe:
 */
public class Main {

    /**
     * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
     *
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     *
     * 判断你是否能够到达最后一个下标。
     *
     * 贪心算法更好实现，从前往后迭代，同时记录当前阶段最远能跳到的地方。
     * 1. 在计算最远能跳到的地方时，一定要校验当前的下标是否超过了最远的下标(这种情况不存在)
     * 2. 看当前下标能到达的位置是否超过跳到的最长位置
     */
    public boolean canJump(int[] nums) {
        if (nums.length <= 1) return true;
        int maxCan = 1, len = nums.length;
        for (int i = 1; i < len; i++) {
            if (i <= maxCan) {
                maxCan = Math.max(maxCan, i+nums[i-1]);
                if (maxCan >= len) return true;
            }
        }
        return false;
    }
}
